package previous.Test_0122;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //1.水果成篮
    //解法1：暴力解法+哈希表
    //解法二：滑动窗口+哈希表
    /*left=0，right=0;
    哈希表来记录；
    进窗口：
    1.right向右移动，哈希表记录水果种类数目
    也就是hash[right]++;
    判断：
    2.如果哈希表的长度也就是hash.length>2,
    出窗口
    那么left向右移动，在移动过程中减少其中一种水果数量，直至为0，也就是hash[left++]--;
    更新结果
    3.当大于而之后就可以来记录最大数量*/

    public int totalFruit1(int[] fruits) {
        int ret=0;
        int n=fruits.length;
        Map<Integer,Integer> hash=new HashMap<Integer,Integer>();
        for (int right = 0,left=0; right < n ; right++) {
            //进窗口
            hash.put(fruits[right], hash.getOrDefault(fruits[right],0)+1);
            //判断：
            while(hash.size()>2){
                //出窗口
                hash.put(fruits[left], hash.getOrDefault(fruits[left],0)-1);
                if(hash.get(fruits[left])==0){
                    hash.remove(fruits[left]);
                }
                left++;
            }
            ret=Math.max(ret,right-left+1);
        }
        return ret;
    }
    public int totalFruit(int[] fruits) {
        int ret=0;
        int n=fruits.length;
       int[] hash=new int[n+1];
        for (int right = 0,left=0,k=0; right < n ; right++) {
            //进窗口
            int m=fruits[right];
            if(hash[m]==0){
                k++;
            }
            hash[m]++;
            //判断：
            while(k>2){
                int h=fruits[left];
                //出窗口
               hash[h]--;
                if(hash[h]==0){
                    k--;
                }
                left++;
            }
            ret=Math.max(ret,right-left+1);
        }

        return ret;
    }
    //3.找到字符串中所有字母的异位词
    /*先记录s2中的字母以及个数和长度。
    进窗口

    判断
    比较是否都有相同字母以及次数；
    如果相同，记录left的位置
    出窗口
    比较完之后，将left向右移动
    如果hash[in]<=hash2[in];count++;
    如果
    通过count来记录有效数字
    */
    public List<Integer> findAnagrams(String s, String p) {
           char[] ss=s.toCharArray();
           char[] pp=p.toCharArray();
           int[] hash1=new int[26];
           int[] hash2=new int[26];
           List<Integer> a=new ArrayList<>(100);
           int n=0;
           int len= pp.length;
        for (int i = 0; i < len; i++) {
            hash2[pp[i]-'a']++;
        }
        int count=0;
        for (int right = 0,left=0; right < s.length(); right++) {
            int in=ss[right]-'a';
            hash1[in]++;
            //进窗口
            //判断是否是有效数字，如果次数小于，那么就是有效个数
            if(hash1[in]<=hash2[in]){
                count++;
            }
            //判断
            //如果left与right的范围大于p长度，那么将left位置的字符个数减小，
            //还要判断有效个数是否等于len，如果相等就是异位词，将left下标添加，left++
            if(right-left+1>len){
                int out=ss[left++]-'a';
                //还要看left移动的位置是否是有效个数，如果是有效个数，那么count--；
                if(hash1[out]--<=hash2[out]){
                    count--;
                }
        }
            //更新结果
            if(count==len){
                a.add(left);
            }
    }
        return a;
}
   //串联所有单词的子串
   public List<Integer> findSubstring1(String s, String[] words) {
        List<Integer> ret=new ArrayList<>();
        Map<String,Integer> hash1=new HashMap<String,Integer>();
       int len = words[0].length(),m= words.length;
       for(int i=0;i< len; i++){// 执行次数
       Map<String,Integer>hash2 = new HashMap<String,Integer>();// 保存窗口内所有单词的频次
       for(int left =i,right =i,count =0;right + len<= s.length();right += len){
           // 进窗口 +维护 count
           String in=s.substring(right,right+len);
       hash2.put(in,hash2.getOrDefault(in,0)+ 1);
       if(hash2.get(in)<= hash1.getOrDefault(in,0))count++;
       //判断
       if(right-left+1>len *m){
           //出窗口+维护 count
           String out = s.substring(left,left + len);
       if(hash2.get(out)<= hash1.getOrDefault(out,0))count--;
       hash2.put(out,hash2.get(out)-1);left += len;}
       // 更新结果
       if(count == m)ret.add(left);
   }
}
       return ret;
    }
    public List<Integer> findSubstring2(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        Map<String, Integer> hash1 = new HashMap<String, Integer>();
        int len = words[0].length(), m = words.length;
        // 统计 words 数组中每个单词及其出现次数
        for (String word : words) {
            hash1.put(word, hash1.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i < len; i++) {
            Map<String, Integer> hash2 = new HashMap<String, Integer>();
            for (int left = i, right = i, count = 0; right + len <= s.length(); right += len) {
                String in = s.substring(right, right + len);
                hash2.put(in, hash2.getOrDefault(in, 0) + 1);
                if (hash2.get(in) <= hash1.getOrDefault(in, 0)) {
                    count++;
                }
                if (right - left + 1 > len * m) {
                    String out = s.substring(left, left + len);
                    if (hash2.get(out) <= hash1.getOrDefault(out, 0)) {
                        count--;
                    }
                    hash2.put(out, hash2.get(out) - 1);
                    left += len;
                }
                if (count == m) {
                    ret.add(left);
                }
            }
        }
        return ret;
    }
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret=new ArrayList<>();
        Map<String,Integer> hash1=new HashMap<String,Integer>();
        for (String str:words) {
            hash1.put(str,hash1.getOrDefault(str,0)+1);
        }
        //单词长度
        int len=words[0].length();
        //单词个数
        int n= words.length;

        //注意：这里是right+len小于单词个数，否则会越界
        for (int i = 0; i < len; i++) {
            Map<String,Integer> hash2=new HashMap<String,Integer>();
            int count=0;
            for (int right = i,left=i; right+len <=s.length() ; right+=len) {
                //进窗口：
                //将right到right+len这一段字符串存到hash2中；
                String in=s.substring(right,right+len);
                //hash.push放入hash表中，前面字符串，后字符串出现的次数
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.get(in)<=hash1.getOrDefault(in,0)){
                    count++;
                }
                //判断
                //随后如果right-left+1>len*m,m也就是单词个数；
                if(right-left+1>len*n){
                    //出窗口
                    //看有效字符个数是否等于单词字符个数，如果相等那么记录left下标
                    //看left下标开始的字符是否在有效字符内，如果有，那么有效字符个数减少
                    String out=s.substring(left,left+len);
                    if(hash2.get(out)<=hash1.getOrDefault(out,0)){
                        count--;
                    }
                    hash2.put(out,hash2.get(out)-1);
                    left+=len;
                }
                //更新结果
                if(count==n){
                    ret.add(left);
                }
            }
        }
        return ret;
    }
    //最小覆盖子串
    public String minWindow(String s, String t) {
        int[] hash1=new int[128];
        char[] tt=t.toCharArray();
        char[] ss=s.toCharArray();
        int m=tt.length;
        if(m>s.length()){
            return "";
        }
        int kind=0;
        for (int i = 0; i <m ; i++) {
            if(hash1[tt[i]]==0){
                kind++;
            }
            hash1[tt[i]]++;
        }
        int[] hash2=new int[128];
        int count=0;
        int min=Integer.MAX_VALUE;
        int begin=-1;
        int left=0;
        for (int right = 0; right < s.length(); right++){
            //进窗口
            char in=ss[right];
            hash2[in]++;
            if(hash2[in]==hash1[in]){
                count++;
            }
            //判断
            while(count==kind){
                char out=ss[left];
                if(hash2[out]--==hash1[out]){
                    count--;
                }
                if(right-left+1<min){
                    begin=left;
                    min=right-left+1;
                }
                left++;
            }
        }
        if(begin==-1){
            return new String();
        }
        return s.substring(begin,begin+min);
    }
}
